﻿using System;
using System.Threading;

namespace ConsoleTest
{
    public class NonBlockingQueue
    {
        // The buffer
        private readonly int[] _buf;

        // Push and Pop indexes. Make them volatile just in case
        private volatile int _pushIndex;
        private volatile int _popIndex;

        // This SpinLock synchronizes parallel writers
        private SpinLock _writerLock = new SpinLock();

        /// <summary>
        /// For simplicity, lets' implement initialization in constructor
        /// This frees us from making it's logic thread-safe
        /// </summary>
        /// <param name="size"></param>
        public NonBlockingQueue(int size)
        {
            if (size <= 0)
                throw new ArgumentException("Invalid size specified");

            _buf = new int[size];
        }

        /// <summary>
        /// Enqueues an element.
        /// Uses a SpinLock to synchronize parallel writers.
        /// </summary>
        /// <param name="value"></param>
        public void Enqueue(int value)
        {
            var wasLocked = false;
            try
            {
                _writerLock.Enter(ref wasLocked);

                // moving push index
                int newPushIndex = (_pushIndex + 1) % _buf.Length;

                if (newPushIndex == _popIndex)
                    throw new InvalidOperationException("Buffer overflow");

                _buf[_pushIndex] = value;
                _pushIndex = newPushIndex;
            }
            finally
            {
                if (wasLocked)
                    _writerLock.Exit(false);
            }
        }

        /// <summary>
        /// Dequeues an element without locks.
        /// </summary>
        /// <returns></returns>
        public int Dequeue()
        {
            int result;

            // Using Interlocked.CompareExchange() to try to win the race.
            // TODO: in theory, a livelock is possible here, so some 
            // resque logic might be necessary.
            int oldPopIndex, newPopIndex;
            do
            {
                oldPopIndex = _popIndex;

                if (oldPopIndex == _pushIndex)
                    throw new InvalidOperationException("Queue is empty");

                newPopIndex = (oldPopIndex + 1) % _buf.Length;

                result = _buf[oldPopIndex];
            } 
            while (oldPopIndex != Interlocked.CompareExchange(ref _popIndex, newPopIndex, oldPopIndex));

            return result;
        }
    }
}
